package lru_demo

import (
	"sort"
	"sync"
)

const (
	valueNotFound = -1
)

type LRUCache struct {
	mtx      sync.Mutex
	data     map[int]*kv
	capacity int // 容量
}
type kv struct {
	id    int // 自增ID
	key   int
	val   int
	count int // 访问次数
}

type autoID struct {
	mtx sync.Mutex
	id  int
}

var a = &autoID{}

// genNextID 生成自增ID.
func (a *autoID) genNextID() int {
	a.mtx.Lock()
	defer a.mtx.Unlock()
	a.id++
	return a.id
}

// NewLRUCache 新建一个LRU缓存对象.
func NewLRUCache(capacity int) *LRUCache {
	return &LRUCache{data: make(map[int]*kv, capacity), capacity: capacity}
}

// Get 获取数据.
func (c *LRUCache) Get(key int) int {
	data := c.data[key]
	if data != nil {
		data.count++
		return data.val
	}
	return valueNotFound
}

// Put 写入数据.
func (c *LRUCache) Put(key int, value int) {
	c.mtx.Lock()
	defer c.mtx.Unlock()
	data := c.data[key]
	// 数据存在处理
	if data != nil {
		c.data[key].val = value
		c.data[key].count++
		return
	}
	// 数据不存在处理
	// 数据满了
	if len(c.data) >= c.capacity {
		// 删除不常用数据
		removeKey := c.FindRemoveID()
		if removeKey != valueNotFound {
			delete(c.data, removeKey)
		}
	}
	// 添加新数据
	c.data[key] = &kv{
		id:  a.genNextID(),
		key: key,
		val: value,
	}
}

// FindRemoveID 查找待淘汰的key.
func (c *LRUCache) FindRemoveID() int {
	if len(c.data) > 0 {
		d := make([]*kv, len(c.data))
		idx := 0
		for i := range c.data {
			d[idx] = c.data[i]
			idx++
		}
		// 排序
		sort.Slice(d, func(i, j int) bool {
			if d[i].count != d[j].count {
				// 访问次数最少
				return d[i].count < d[j].count
			}
			// id最小
			return d[i].id < d[j].id
		})
		return d[0].key
	}
	return valueNotFound
}
